Generally, a microprocessor includes an Arithmetic and Logic Unit (ALU) for performing the four arithmetic operations. In the ALU, every integer number X is represented in the form of a bit string using the so-called two's complement coding. Indicating with Xk a generic bit of a string of N bits representing the number X∈└−2N-1, 2N-1−1┘, the integer number X is given by
                    X        =                                            ∑                              k                =                0                                            N                -                2                                      ⁢                                                  ⁢                                          X                k                            ·                              2                k                                              -                                    X                              N                -                1                                      ·                          2                              N                -                1                                                                        (        1        )            
This coding is very convenient because it allows the difference operation to be performed as a sum of relative numbers using a common adder.
The two's complement of a bit string X may be easily obtained by logic circuits. In fact, indicating with X the one's complement of X is given by X=2N−1−X  (2)which is obtained by inverting each bit of the string X. The string YTC(X) representing the two's complement of X is simply obtained adding 1 to the one's complement of X is given byYTC(X)= X+1=2N−X  (3)
A two's complement circuit is depicted in FIG. 1. The two's complement circuit of the ALU may be used for performing increment or decrement operations. The circuit of FIG. 2 increments by one the string X because the string X+1 is the two's complement of the one's complement of the string X is given byX+1= X+1=( X)+1=YTC( X)  (4)
Similarly, it is possible to demonstrate that the circuit of FIG. 3 decrements by one the string X, because the string X−1 is the one's complement of the two's complement of the string X is given byX−1=2N−2N+X−1=2N−1−(2N−X)=2N−1−YTC(X)= YTC(X)  (5)
The fact that these increment and decrement operations can be performed by a two's complement circuit has lead to the realization of the so-called DIT (Decrement, Increment, Two's complement) circuits, such as the one depicted in FIG. 4. This circuit is substantially formed by a logic selection circuit SEL generating logic signals INV_IN and INV_OUT, by an array of input XOR gates input with the bits of the string X and the signal INV_IN, and by an array of XOR output gates receiving the bits of the two's complement string and the signal INV_OUT. The circuit of FIG. 4 performs a decrement, increment or two's complement operation, with the logic state of the commands ID and TC being determined according to the following table
TABLE 1IDTCOPERATIONINV_ININV_OUT00Decrement0110Increment10—1two's00
Because of the importance of the DIT circuit, the architecture thereof has been studied to find two's complement circuits that imply the smallest possible number of required elementary operations and that occupy the smallest possible silicon area. In the articles by R. Hashemian “Highly Parallel Increment/Decrement Using CMOS Technology”, Proceedings of the 33rd Midwest Symposium on Circuits and Systems, Calgari, Alberta, Canada, Aug. 12-14, 1990 and by R. Hashemian and C. Chen “A New Parallel Technique For Design of Decrement/Increment and Two's Complement Circuits”, Proceedings of the 34th Midwest Symposium on Circuits and Systems, Monteray, Calif., May 14-17, 1991 techniques for forming decrement, increment and two's complement circuits are described, that offer certain advantages both in terms of silicon area consumption as well as in terms of speed.
By applying eq. 3, it is possible to note that the two's complement of the number −2N-1 is the number −2N-1 itself. This fact is due to the asymmetry of the interval X∈└−2N-1, 2N-1−1┘, thus the two's complement of −2N-1 exceeds the representation interval.
In many applications the two's complement of −2N-1 is represented with the positive integer 2N-11YTC(−2N-1)=2N-1−1= X  (6)generating at the same time an overflow flag OF signaling that the representation interval has been exceeded.
A known two's complement circuit with overflow check is depicted in FIG. 5. It generates an overflow flag OF when the string to be complemented represents the number −2N-1, and has a correction circuit CLIP that receives a two's complement string Z and the overflow flag OF, generating the correct output string Y.
The overflow check circuit OVERFLOW CHECK is input with the string X and with a string REF representing the number −2N-1, and activates the flag OF when the two strings coincide. The correction circuit CLIP generates an output string Y equal to the two's complement string Z when the flag OF is not active, while it produces the string 011 . . . 1 representing the number 2N-1−1 when the flag OF is active. Unfortunately, the known two's complement circuit depicted in FIG. 5 is not convenient because the circuit OVERFLOW CHECK is an N bit comparator, whose silicon area occupation depends on the number of bits of the string X.